package com.example.jianzhioffer;

import java.util.ArrayList;

/**
 * Created by Quincy on 2018/9/20.
 * 输入一颗二叉树和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。
 * 路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。
 */
public class PrintTreeNodeSumK {
    public class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;

        public TreeNode(int val) {
            this.val = val;

        }
    }

    private ArrayList<ArrayList<Integer>> listall = new ArrayList<ArrayList<Integer>>();

    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root, int target) {

        ArrayList<Integer> list = new ArrayList<Integer>();
        if (root == null){
            return listall;
        }
        int cursum = 0;
        return FindPath(root, target, list, cursum);
    }

    //递归调用，存储有效路径
    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root, int target, ArrayList<Integer> list, int cursum){
        cursum += root.val;
        list.add(root.val);
        //发现路径函数
        if (cursum == target && root.left == null && root.right == null){
            ArrayList<Integer> path = new ArrayList<>();
            for (int i = 0; i < list.size(); i++){
                path.add(list.get(i));
            }
            listall.add(path);
        }

        // 如果小于当前值，且左子树不为空，则向左子树进发
        if (cursum < target && root.left != null) {
            FindPath(root.left, target, list, cursum);
        }
        // 如果小于当前值，且右子树不为空，则向右子树进发
        if (cursum < target && root.right != null) {
            FindPath(root.right, target, list, cursum);
        }
        //如果当前路径值和大于目标值或者已经找到一条路径则回到上一层
        cursum -= root.val;
        list.remove(list.size() - 1);
        return listall;
    }
}
